package com.shuang.tree23;

public class IsSubtree {

    //递归实现
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {

        //判断
        // subRoot为 null 一定都是 true
        if (subRoot == null) {
            return true;
        }
        // subRoot一定不为 null, 只要 root 为 null，肯定是 false
        if (root == null) {
            return false;
        }
        //root subRoot都不为空 判断 这两棵树是否是相等的树 是的话直接返回true
        if (isSameTree(root, subRoot)) {
            return true;
        }

        //不是相等的树 判断 subRoot是否是root的子树 即判断root 左和右子树 是否有和subRoot相等的
        boolean leftSame = isSubtree(root.left, subRoot);
        boolean rightSame = isSubtree(root.right, subRoot);
        boolean result = leftSame || rightSame; //左子树和右子树 有一个和subRoot判断成功即为真

        return result;

    }

    //判断两棵树是否相等
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //递归实现

        //判断节点情况
        if (p == null && q == null) {
            return true;
        }

        if (p == null || q == null || p.val != q.val) {
            return false;
        }

        //节点都不为空 且值相等 接着往下走 相当于后序 处理左 右 中的顺序
        boolean leftSame = isSameTree(p.left, q.left);
        boolean rightSame = isSameTree(p.right, q.right);
        boolean result = leftSame && rightSame;

        return result;
    }
}
